import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class Solution678 {

    private boolean doJudge(List<Integer> bracketList, List<Integer> starList){
        for (Integer bracketLoc:bracketList) {
            boolean isProb = false;
            for (Integer starLoc:starList) {
                if(bracketLoc < starLoc){
                    starList.remove(starLoc);
                    isProb = true;
                    break;
                }
            }
            if(!isProb){
                return false;
            }
        }
        return true;
    }

    public boolean checkValidString(String s) {
        List<Integer> bracketList = new ArrayList<>();
        List<Integer> starList = new LinkedList<>();
        for (int i = 0; i < s.length(); i++) {
            char tmpC = s.charAt(i);
            if(tmpC == '('){
                bracketList.add(i);
            }
            else if(tmpC == '*'){
                starList.add(i);
            }
            else{
                if(bracketList.size() > 0){
                    bracketList.remove(bracketList.size()-1);
                }
                else if(starList.size() > 0){
                    starList.remove(0);
                }
                else{
                    return false;
                }
            }
        }
        if(bracketList.size() == 0 || doJudge(bracketList, starList)){
            return true;
        }
        return false;
    }

    public static void main(String[] args) {
        Solution678 s = new Solution678();
        System.out.println(s.checkValidString("(((((*(()((((*((**(((()()*)()()()*((((**)())*)*)))))))(())(()))())((*()()(((()((()*(())*(()**)()(())"));
    }
}
